The present invention generally relates to routing wires in an integrated circuit design and, in particular, to techniques for routing signal wires in an integrated circuit design.
Wire routing (routing) is one step in the electronic design of integrated circuits (ICs) and printed circuit boards (PCBs). Wire routing builds on a preceding placement step, which determines the location of each active element of an IC or component on a PCB. After placement, the routing step adds wires needed to properly connect the placed elements or components while obeying all design rules. Routers are typically provided with pre-existing polygons for pins (or terminals) of cells and some pre-existing wiring (or pre-routes). Each of the polygons are associated with a net, usually by name or number. The primary task of a router is to create geometries such that all terminals assigned to the same net are connected, no terminals assigned to different nets are connected, and all design rules are obeyed.
A router can fail by not connecting terminals that should be connected (an open), by connecting two terminals that should not be connected (a short), and/or by violating a design rule. Routers may also be configured to ensure an electronic design meets timing requirements, has no crosstalk problems, meets any metal density requirements, and/or does not suffer from antenna effects, etc. Almost every problem associated with routing is known to be intractable. The simplest routing problem (commonly referred to as a Steiner Tree Problem) of finding the shortest route for one net in one layer with no design rules is NP-hard, even if only horizontal and vertical wires are allowed. Variants of channel routing, as well as routing to reduce crosstalk, the number of vias, etc., have also been shown to be NP-complete. In practice, routers seldom attempt to find an optimum result. That is, routers typically attempt to find a solution that is good enough based on some established criteria.
Design rules for ICs sometimes vary considerably from layer to layer. For example, the allowed width and spacing on lower metal layers may be four or more times smaller than the allowed width and spacing on upper metal layers. Different wire width and wire spacing for different metal layers of an IC results in additional complications not faced by routers for other applications, e.g., PCB or multi-chip module (MCM) design. In particular, difficulties ensue if the design rules are not simple multiples of each other and when vias must traverse between layers with different rules. The earliest types of electronic design automation (EDA) routers were manual routers, i.e., a designer clicked a mouse on an endpoint of each line segment of each net to route a wire. Modern electronic design software typically provides interactive routers, i.e., a designer selects a pad and clicks a few places to give the router an idea of where to go and the router attempts to place wires as close to that path as possible without violating design rules.
Some more advanced interactive routers have ‘push’ and ‘shove’ features that allow the routers to push nets out of the way, if possible, in order to place a new wire where a designer wants the wire and still avoid violating design rules. Modern EDA software also typically provides auto-routers, which route remaining un-routed connections without human intervention. Auto-routers may take various forms. For example, an auto-router may take the form of a maze router, a line probe router, a channel router, an area router, or a switchbox router. An auto-router may, for example, first determine an approximate course for each net, e.g., route on a coarse grid or perform global routing. In general, global routing limits the size and complexity of subsequent detailed routing steps, which can be done square-by-square on a routing grid.
For detailed routing, the most common technique is rip-up and reroute, which includes: selecting a sequence in which the nets are to be routed; routing each net in the sequence; and, if not all nets can be successfully routed, applying any of a variety of clean-up methods, in which selected routings are removed, the order of the remaining nets to be routed is changed, and the remaining routings are attempted again. In general, the rip-up and reroute technique repeats until all nets are routed or the routing program (or a user of the program) gives up. An alternative multi-pass iterative-improvement routing approach treats shorts, design rule violations, obstructions, etc. on a similar footing as excess wire length, i.e., as finite costs to be reduced (at first) rather than as absolutes to be avoided. The multi-pass iterative-improvement routing approach, for each of several iterative passes, includes: prescribing or adjusting weight parameters of an objective function (having a weight parameter value for each unit of excess wire length, and for each type of design rule violation).
For example, in the multi-pass iterative-improvement routing approach, during a first pass excess wire length may typically be given a high cost, while design violations such as shorts, adjacency, etc. are given a low cost. In later passes, the relative ordering of costs is changed so that violations are high-cost or may be prohibited. A sequence in which nets are to be routed during the pass are then selected or randomly chosen. Each net, in turn, is then ripped-up (if previously routed) and re-routed so as to minimize the value of the objective function for the net. Typically, some of the routings will have shorts or other design rule violations. A next iterative pass is then processed until routing is complete and correct, is not further improved, or some other termination criterion is satisfied. Most routers assign wiring layers to carry predominantly ‘x’ or ‘y’ directional wiring, although there are routers that avoid or reduce the need for directional wiring assignment. In general, restricting wiring direction simplifies power supply design and control of inter-layer crosstalk. However, allowing arbitrary routes may reduce the need for vias and decrease the number of required wiring layers.